/*
 * @lc app=leetcode.cn id=35 lang=swift
 *
 * [35] 搜索插入位置
 */

// @lc code=start
class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        var left = 0, right = nums.count - 1
        var middle = 0
        while left <= right {
            middle = (left + right) / 2
            if nums[middle] > target {
                right = middle - 1
            } else if nums[middle] < target {
                left = middle + 1
                middle += 1
            } else {
                return middle
            }
        }
        return middle < 0 ? 0 : middle
    }
}
// @lc code=end

